import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

public class Trap {
    // leetcode hot 100 接雨水
    // https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked

    /**
     * 方法一：使用双指针
     * @param height
     * @return
     */
    public int trap(int[] height) {
        // 使用双指针，分别计算出数组中每个位置左边的最高的柱子以及右边最高的柱子
        // 最终接的雨水的体积就是
        // 数组中每个位置最左边最高的柱子和右边最高的柱子中较小值-当前位置柱子的高度之和
        int length = height.length;
        int[] maxLeft = new int[length];
        int[] maxRight = new int[length];
        maxLeft[0] = height[0];
        for (int i = 1; i < length; i++) {
            maxLeft[i] = Math.max(height[i-1],maxLeft[i-1]);
        }
        maxRight[length-1] = height[length-1];
        for (int i = length -21; i >= 0; i--) {
            maxRight[i] = Math.max(height[i+1],maxRight[i+1]);
        }
        // 求和
        int sum = 0;
        for (int i = 0; i < length; i++) {
            int count = Math.min(maxLeft[i],maxRight[i]) - height[i];
            if (count > 0) sum += count;
        }
        return sum;
    }

    /**
     * 单调栈解决
     * 从栈顶到栈底的元素的大小是递增的，遍历数组中的元素，如果小于栈顶元素，则加入栈顶，否则就从栈顶中弹出一个元素，这个就是积雨水的部分
     * 然后在从栈顶中取出来一个元素（peek不是poll）left，然后取height[left]和height[i]中的较小值作为高，计算积水的容量
     * @param height
     * @return
     */
    public int trap1(int[] height) {
        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(0);
        int ret = 0;
        for (int i = 1; i < height.length; i++) {
            while (!deque.isEmpty() && height[i] > height[deque.peekFirst()]) {
                if (deque.size() >= 2) {
                    int low = deque.removeFirst(), left = deque.peekFirst();
                    ret += (i-left-1) * (Math.min(height[i],height[left])-height[low]);
                }else {
                    deque.removeFirst();
                }
            }
            deque.addFirst(i);
        }
        return ret;
    }

    public static void main(String[] args) {
        Trap trap = new Trap();
        int[] arr = {0,1,0,2,1,0,1,3,2,1,2,1};
        trap.trap(arr);
    }
}
